{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2025 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# rcpsp_sat"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/examples/rcpsp_sat.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/examples/python/rcpsp_sat.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "description",
   "metadata": {},
   "source": [
    "\n",
    "Sat based solver for the RCPSP problems (see rcpsp.proto).\n",
    "\n",
    "Introduction to the problem:\n",
    "   https://www.projectmanagement.ugent.be/research/project_scheduling/rcpsp\n",
    "\n",
    "Data use in flags:\n",
    "  http://www.om-db.wi.tum.de/psplib/data.html\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "\n",
    "from ortools.sat.colab import flags\n",
    "from google.protobuf import text_format\n",
    "from ortools.sat.python import cp_model\n",
    "from ortools.scheduling import rcpsp_pb2\n",
    "from ortools.scheduling.python import rcpsp\n",
    "\n",
    "_INPUT = flags.define_string(\"input\", \"\", \"Input file to parse and solve.\")\n",
    "_OUTPUT_PROTO = flags.define_string(\n",
    "    \"output_proto\", \"\", \"Output file to write the cp_model proto to.\"\n",
    ")\n",
    "_PARAMS = flags.define_string(\"params\", \"\", \"Sat solver parameters.\")\n",
    "_USE_INTERVAL_MAKESPAN = flags.define_bool(\n",
    "    \"use_interval_makespan\",\n",
    "    True,\n",
    "    \"Whether we encode the makespan using an interval or not.\",\n",
    ")\n",
    "_HORIZON = flags.define_integer(\"horizon\", -1, \"Force horizon.\")\n",
    "\n",
    "\n",
    "def print_problem_statistics(problem: rcpsp_pb2.RcpspProblem):\n",
    "    \"\"\"Display various statistics on the problem.\"\"\"\n",
    "\n",
    "    # Determine problem type.\n",
    "    problem_type = (\n",
    "        \"Resource Investment Problem\" if problem.is_resource_investment else \"RCPSP\"\n",
    "    )\n",
    "\n",
    "    num_resources = len(problem.resources)\n",
    "    num_tasks = len(problem.tasks) - 2  # 2 sentinels.\n",
    "    tasks_with_alternatives = 0\n",
    "    variable_duration_tasks = 0\n",
    "    tasks_with_delay = 0\n",
    "\n",
    "    for task in problem.tasks:\n",
    "        if len(task.recipes) > 1:\n",
    "            tasks_with_alternatives += 1\n",
    "            duration_0 = task.recipes[0].duration\n",
    "            for recipe in task.recipes:\n",
    "                if recipe.duration != duration_0:\n",
    "                    variable_duration_tasks += 1\n",
    "                    break\n",
    "        if task.successor_delays:\n",
    "            tasks_with_delay += 1\n",
    "\n",
    "    if problem.is_rcpsp_max:\n",
    "        problem_type += \"/Max delay\"\n",
    "    # We print 2 less tasks as these are sentinel tasks that are not counted in\n",
    "    # the description of the rcpsp models.\n",
    "    if problem.is_consumer_producer:\n",
    "        print(f\"Solving {problem_type} with:\")\n",
    "        print(f\"  - {num_resources} reservoir resources\")\n",
    "        print(f\"  - {num_tasks} tasks\")\n",
    "    else:\n",
    "        print(f\"Solving {problem_type} with:\")\n",
    "        print(f\"  - {num_resources} renewable resources\")\n",
    "        print(f\"  - {num_tasks} tasks\")\n",
    "        if tasks_with_alternatives:\n",
    "            print(f\"    - {tasks_with_alternatives} tasks with alternative resources\")\n",
    "        if variable_duration_tasks:\n",
    "            print(f\"    - {variable_duration_tasks} tasks with variable durations\")\n",
    "        if tasks_with_delay:\n",
    "            print(f\"    - {tasks_with_delay} tasks with successor delays\")\n",
    "\n",
    "\n",
    "def solve_rcpsp(\n",
    "    problem: rcpsp_pb2.RcpspProblem,\n",
    "    proto_file: str,\n",
    "    params: str,\n",
    "    active_tasks: set[int],\n",
    "    source: int,\n",
    "    sink: int,\n",
    ") -> None:\n",
    "    \"\"\"Parse and solve a given RCPSP problem in proto format.\n",
    "\n",
    "    The model will only look at the tasks {source} + {sink} + active_tasks, and\n",
    "    ignore all others.\n",
    "\n",
    "    Args:\n",
    "      problem: the description of the model to solve in protobuf format\n",
    "      proto_file: the name of the file to export the CpModel proto to.\n",
    "      params: the string representation of the parameters to pass to the sat\n",
    "        solver.\n",
    "      active_tasks: the set of active tasks to consider.\n",
    "      source: the source task in the graph. Its end will be forced to 0.\n",
    "      sink: the sink task of the graph. Its start is the makespan of the problem.\n",
    "\n",
    "    Returns:\n",
    "      (lower_bound of the objective, best solution found, assignment)\n",
    "    \"\"\"\n",
    "    # Create the model.\n",
    "    model = cp_model.CpModel()\n",
    "    model.name = problem.name\n",
    "\n",
    "    num_resources = len(problem.resources)\n",
    "\n",
    "    all_active_tasks = list(active_tasks)\n",
    "    all_active_tasks.sort()\n",
    "    all_resources = range(num_resources)\n",
    "\n",
    "    horizon = problem.deadline if problem.deadline != -1 else problem.horizon\n",
    "    if _HORIZON.value > 0:\n",
    "        horizon = _HORIZON.value\n",
    "    elif horizon == -1:  # Naive computation.\n",
    "        horizon = sum(max(r.duration for r in t.recipes) for t in problem.tasks)\n",
    "        if problem.is_rcpsp_max:\n",
    "            for t in problem.tasks:\n",
    "                for sd in t.successor_delays:\n",
    "                    for rd in sd.recipe_delays:\n",
    "                        for d in rd.min_delays:\n",
    "                            horizon += abs(d)\n",
    "    print(f\"Horizon = {horizon}\", flush=True)\n",
    "\n",
    "    # Containers.\n",
    "    task_starts = {}\n",
    "    task_ends = {}\n",
    "    task_durations = {}\n",
    "    task_intervals = {}\n",
    "    task_resource_to_energy = {}\n",
    "    task_to_resource_demands = collections.defaultdict(list)\n",
    "\n",
    "    task_to_presence_literals = collections.defaultdict(list)\n",
    "    task_to_recipe_durations = collections.defaultdict(list)\n",
    "    task_resource_to_fixed_demands = collections.defaultdict(dict)\n",
    "    task_resource_to_max_energy = collections.defaultdict(int)\n",
    "\n",
    "    resource_to_sum_of_demand_max = collections.defaultdict(int)\n",
    "\n",
    "    # Create task variables.\n",
    "    for t in all_active_tasks:\n",
    "        task = problem.tasks[t]\n",
    "        num_recipes = len(task.recipes)\n",
    "        all_recipes = range(num_recipes)\n",
    "\n",
    "        start_var = model.new_int_var(0, horizon, f\"start_of_task_{t}\")\n",
    "        end_var = model.new_int_var(0, horizon, f\"end_of_task_{t}\")\n",
    "\n",
    "        if num_recipes > 1:\n",
    "            # Create one literal per recipe.\n",
    "            literals = [model.new_bool_var(f\"is_present_{t}_{r}\") for r in all_recipes]\n",
    "\n",
    "            # Exactly one recipe must be performed.\n",
    "            model.add_exactly_one(literals)\n",
    "\n",
    "        else:\n",
    "            literals = [1]\n",
    "\n",
    "        # Temporary data structure to fill in 0 demands.\n",
    "        demand_matrix = collections.defaultdict(int)\n",
    "\n",
    "        # Scan recipes and build the demand matrix and the vector of durations.\n",
    "        for recipe_index, recipe in enumerate(task.recipes):\n",
    "            task_to_recipe_durations[t].append(recipe.duration)\n",
    "            for demand, resource in zip(recipe.demands, recipe.resources):\n",
    "                demand_matrix[(resource, recipe_index)] = demand\n",
    "\n",
    "        # Create the duration variable from the accumulated durations.\n",
    "        duration_var = model.new_int_var_from_domain(\n",
    "            cp_model.Domain.from_values(task_to_recipe_durations[t]),\n",
    "            f\"duration_of_task_{t}\",\n",
    "        )\n",
    "\n",
    "        # Link the recipe literals and the duration_var.\n",
    "        for r in range(num_recipes):\n",
    "            model.add(duration_var == task_to_recipe_durations[t][r]).only_enforce_if(\n",
    "                literals[r]\n",
    "            )\n",
    "\n",
    "        # Create the interval of the task.\n",
    "        task_interval = model.new_interval_var(\n",
    "            start_var, duration_var, end_var, f\"task_interval_{t}\"\n",
    "        )\n",
    "\n",
    "        # Store task variables.\n",
    "        task_starts[t] = start_var\n",
    "        task_ends[t] = end_var\n",
    "        task_durations[t] = duration_var\n",
    "        task_intervals[t] = task_interval\n",
    "        task_to_presence_literals[t] = literals\n",
    "\n",
    "        # Create the demand variable of the task for each resource.\n",
    "        for res in all_resources:\n",
    "            demands = [demand_matrix[(res, recipe)] for recipe in all_recipes]\n",
    "            task_resource_to_fixed_demands[(t, res)] = demands\n",
    "            demand_var = model.new_int_var_from_domain(\n",
    "                cp_model.Domain.from_values(demands), f\"demand_{t}_{res}\"\n",
    "            )\n",
    "            task_to_resource_demands[t].append(demand_var)\n",
    "\n",
    "            # Link the recipe literals and the demand_var.\n",
    "            for r in all_recipes:\n",
    "                model.add(demand_var == demand_matrix[(res, r)]).only_enforce_if(\n",
    "                    literals[r]\n",
    "                )\n",
    "\n",
    "            resource_to_sum_of_demand_max[res] += max(demands)\n",
    "\n",
    "        # Create the energy expression for (task, resource):\n",
    "        for res in all_resources:\n",
    "            task_resource_to_energy[(t, res)] = sum(\n",
    "                literals[r]\n",
    "                * task_to_recipe_durations[t][r]\n",
    "                * task_resource_to_fixed_demands[(t, res)][r]\n",
    "                for r in all_recipes\n",
    "            )\n",
    "            task_resource_to_max_energy[(t, res)] = max(\n",
    "                task_to_recipe_durations[t][r]\n",
    "                * task_resource_to_fixed_demands[(t, res)][r]\n",
    "                for r in all_recipes\n",
    "            )\n",
    "\n",
    "    # Create makespan variable\n",
    "    makespan = model.new_int_var(0, horizon, \"makespan\")\n",
    "    makespan_size = model.new_int_var(1, horizon, \"interval_makespan_size\")\n",
    "    interval_makespan = model.new_interval_var(\n",
    "        makespan,\n",
    "        makespan_size,\n",
    "        model.new_constant(horizon + 1),\n",
    "        \"interval_makespan\",\n",
    "    )\n",
    "\n",
    "    # Add precedences.\n",
    "    if problem.is_rcpsp_max:\n",
    "        # In RCPSP/Max problem, precedences are given and max delay (possible\n",
    "        # negative) between the starts of two tasks.\n",
    "        for task_id in all_active_tasks:\n",
    "            task = problem.tasks[task_id]\n",
    "            num_modes = len(task.recipes)\n",
    "\n",
    "            for successor_index, next_id in enumerate(task.successors):\n",
    "                delay_matrix = task.successor_delays[successor_index]\n",
    "                num_next_modes = len(problem.tasks[next_id].recipes)\n",
    "                for m1 in range(num_modes):\n",
    "                    s1 = task_starts[task_id]\n",
    "                    p1 = task_to_presence_literals[task_id][m1]\n",
    "                    if next_id == sink:\n",
    "                        delay = delay_matrix.recipe_delays[m1].min_delays[0]\n",
    "                        model.add(s1 + delay <= makespan).only_enforce_if(p1)\n",
    "                    else:\n",
    "                        for m2 in range(num_next_modes):\n",
    "                            delay = delay_matrix.recipe_delays[m1].min_delays[m2]\n",
    "                            s2 = task_starts[next_id]\n",
    "                            p2 = task_to_presence_literals[next_id][m2]\n",
    "                            model.add(s1 + delay <= s2).only_enforce_if([p1, p2])\n",
    "    else:\n",
    "        # Normal dependencies (task ends before the start of successors).\n",
    "        for t in all_active_tasks:\n",
    "            for n in problem.tasks[t].successors:\n",
    "                if n == sink:\n",
    "                    model.add(task_ends[t] <= makespan)\n",
    "                elif n in active_tasks:\n",
    "                    model.add(task_ends[t] <= task_starts[n])\n",
    "\n",
    "    # Containers for resource investment problems.\n",
    "    capacities = []  # Capacity variables for all resources.\n",
    "    max_cost = 0  # Upper bound on the investment cost.\n",
    "\n",
    "    # Create resources.\n",
    "    for res in all_resources:\n",
    "        resource = problem.resources[res]\n",
    "        c = resource.max_capacity\n",
    "        if c == -1:\n",
    "            print(f\"No capacity: {resource}\")\n",
    "            c = resource_to_sum_of_demand_max[res]\n",
    "\n",
    "        # RIP problems have only renewable resources, and no makespan.\n",
    "        if problem.is_resource_investment or resource.renewable:\n",
    "            intervals = [task_intervals[t] for t in all_active_tasks]\n",
    "            demands = [task_to_resource_demands[t][res] for t in all_active_tasks]\n",
    "\n",
    "            if problem.is_resource_investment:\n",
    "                capacity = model.new_int_var(0, c, f\"capacity_of_{res}\")\n",
    "                model.add_cumulative(intervals, demands, capacity)\n",
    "                capacities.append(capacity)\n",
    "                max_cost += c * resource.unit_cost\n",
    "            else:  # Standard renewable resource.\n",
    "                if _USE_INTERVAL_MAKESPAN.value:\n",
    "                    intervals.append(interval_makespan)\n",
    "                    demands.append(c)\n",
    "\n",
    "                model.add_cumulative(intervals, demands, c)\n",
    "        else:  # Non empty non renewable resource. (single mode only)\n",
    "            if problem.is_consumer_producer:\n",
    "                reservoir_starts = []\n",
    "                reservoir_demands = []\n",
    "                for t in all_active_tasks:\n",
    "                    if task_resource_to_fixed_demands[(t, res)][0]:\n",
    "                        reservoir_starts.append(task_starts[t])\n",
    "                        reservoir_demands.append(\n",
    "                            task_resource_to_fixed_demands[(t, res)][0]\n",
    "                        )\n",
    "                model.add_reservoir_constraint(\n",
    "                    reservoir_starts,\n",
    "                    reservoir_demands,\n",
    "                    resource.min_capacity,\n",
    "                    resource.max_capacity,\n",
    "                )\n",
    "            else:  # No producer-consumer. We just sum the demands.\n",
    "                model.add(\n",
    "                    cp_model.LinearExpr.sum(\n",
    "                        [task_to_resource_demands[t][res] for t in all_active_tasks]\n",
    "                    )\n",
    "                    <= c\n",
    "                )\n",
    "\n",
    "    # Objective.\n",
    "    if problem.is_resource_investment:\n",
    "        objective = model.new_int_var(0, max_cost, \"capacity_costs\")\n",
    "        model.add(\n",
    "            objective\n",
    "            == sum(\n",
    "                problem.resources[i].unit_cost * capacities[i]\n",
    "                for i in range(len(capacities))\n",
    "            )\n",
    "        )\n",
    "    else:\n",
    "        objective = makespan\n",
    "\n",
    "    model.minimize(objective)\n",
    "\n",
    "    # Add sentinels.\n",
    "    task_starts[source] = 0\n",
    "    task_ends[source] = 0\n",
    "    task_to_presence_literals[0].append(True)\n",
    "    task_starts[sink] = makespan\n",
    "    task_to_presence_literals[sink].append(True)\n",
    "\n",
    "    # Write model to file.\n",
    "    if proto_file:\n",
    "        print(f\"Writing proto to{proto_file}\")\n",
    "        model.export_to_file(proto_file)\n",
    "\n",
    "    # Solve model.\n",
    "    solver = cp_model.CpSolver()\n",
    "\n",
    "    # Parse user specified parameters.\n",
    "    if params:\n",
    "        text_format.Parse(params, solver.parameters)\n",
    "\n",
    "    # Favor objective_shaving over objective_lb_search.\n",
    "    if solver.parameters.num_workers >= 16 and solver.parameters.num_workers < 24:\n",
    "        solver.parameters.ignore_subsolvers.append(\"objective_lb_search\")\n",
    "        solver.parameters.extra_subsolvers.append(\"objective_shaving\")\n",
    "\n",
    "    # Experimental: Specify the fact that the objective is a makespan\n",
    "    solver.parameters.push_all_tasks_toward_start = True\n",
    "\n",
    "    # Enable logging in the main solve.\n",
    "    solver.parameters.log_search_progress = True\n",
    "\n",
    "    # Solve the model.\n",
    "    solver.solve(model)\n",
    "\n",
    "\n",
    "def main(_):\n",
    "    rcpsp_parser = rcpsp.RcpspParser()\n",
    "    rcpsp_parser.parse_file(_INPUT.value)\n",
    "\n",
    "    problem = rcpsp_parser.problem()\n",
    "    print_problem_statistics(problem)\n",
    "\n",
    "    last_task = len(problem.tasks) - 1\n",
    "\n",
    "    solve_rcpsp(\n",
    "        problem=problem,\n",
    "        proto_file=_OUTPUT_PROTO.value,\n",
    "        params=_PARAMS.value,\n",
    "        active_tasks=set(range(1, last_task)),\n",
    "        source=0,\n",
    "        sink=last_task,\n",
    "    )\n",
    "\n",
    "\n",
    "main()\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
